package com.ydc.ln.tutorial.algorithm;

/**
 * 算法小全 之 图论算法
 * 
 * <pre>
 * 1.最小生成树
 * </pre>
 * 
 * @author yangdc
 * 
 */
public class Algorithm02 {

	/**
	 * 最小生成树
	 * 
	 * <pre>
	 * 在一个具有几个顶点的连通图G中，
	 * 如果存在子图G'包含G中所有顶点和一部分边，
	 * 且不形成回路，则称G'为图G的生成树，
	 * 代价最小生成树则称为最小生成树。 
	 * 
	 * 
	 * 许多应用问题都是一个求无向连通图的最小生成树问题。
	 * 例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，
	 * 但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；
	 * 另一个目标是要使铺设光缆的总费用最低。
	 * 这就需要找到带权的最小生成树。
	 * </pre>
	 */
	public void prim() {
		// 构造无向图
		int[][] map = new int[7][7];
		// 初始化权值
		for (int i=0; i<map.length; i++) {
			for (int j=0; j<map[i].length; j++) {
				map[i][j] = 0;
			}
		}
		map[3][4] = 1;
		map[1][3] = map[3][6] = map[4][6] = 2;
		map[1][4] = map[2][5] = 3;
		map[1][2] = map[2][4] = map[5][6] = 4;
		map[2][3] = 5;
		map[4][6] = 6;
		
		
	}
}
